package leetcode.dp;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/longest-increasing-subsequence/
 * <p>
 * nums = [10,9,2,5,3,7,101,18]
 * 1 1 1 1 1 1  1  1
 * <p>
 * 最长递增子序列是 [2,3,7,101]，因此长度为 4 。
 *
 * @author mazouri
 * @create 2021-09-17 19:48
 */
public class _300_lengthOfLIS {
    public int lengthOfLIS(int[] nums) {
        int max = 1;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }

            max = Math.max(dp[i],max);
        }

        return max;
    }
}
